# -*- coding: utf-8 -*-
# @Time: 2021/8/25 10:03
# @File: qiuck_sort.py
# @DESC: 快速排序，找到一个pivot，将小于这个数的放在左边，大于这个数的放右边

def quick_sort(nums, left, right):
    print(nums)
    # 记录两个端点的位置，循环结束之后要依据它们找子序列的端点
    l = left
    r = right
    key = nums[l]
    while l < r:
        # 处理右边向左边移的问题
        while l < r and nums[r] >= key:
            r -= 1
        # 如果此时左小于右，说明是由于nums[r]<key退出的那个循环，=>此时右值比左值小，将其移动到左边去
        if l < r:
            nums[l] = nums[r]
            # 由于左边第一个值固定了，所以左边的移动位置就+1
            l += 1
        # 处理右边向左边移动的问题
        while l < r and nums[l] <= key:
            # 当前值比标定值小，继续向前移动
            l += 1
        # 此时如果左小于右，说明nums[l]>=key退出的while循环，=>此时的左值比key更大，将其移动到右边去
        if l < r:
            nums[r] = nums[l]
            # 此时最右边的值就已经找到位置了，将下标向前移动
            r -= 1
    # 退出上面的循环，说明l==r，两个点相遇了，此时将key赋值到这个位置
    nums[l] = key

    # 此时已经分出了左、右子序列，进行递归调用
    quick_sort(nums, 0, l - 1)
    quick_sort(nums, l + 1, right)


nums = [1, 4, 6, 7, 1, 3, 6, 7, 0, 1]

quick_sort(nums, 0, len(nums))

print(nums)
